package mine.code.day.year2021.month08;

import org.junit.Test;

/**
 * 给你一个正整数数组arr，请你计算所有可能的奇数长度子数组的和。
 * <p>
 * 子数组 定义为原数组中的一个连续子序列。
 * <p>
 * 请你返回 arr中 所有奇数长度子数组的和 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [1,4,2,5,3]
 * 输出：58
 * 解释：所有奇数长度子数组和它们的和为：
 * [1] = 1
 * [4] = 4
 * [2] = 2
 * [5] = 5
 * [3] = 3
 * [1,4,2] = 7
 * [4,2,5] = 11
 * [2,5,3] = 10
 * [1,4,2,5,3] = 15
 * <p>
 * 我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
 *
 * @author caijinnan
 */
public class Day29_所有奇数长度子数组的和 {

    @Test
    public void run() {
        //           3,4,5,4,3 -> 3+16+10+20+9
        int[] arr = {1, 4, 2, 5, 3};
        System.out.println(sumOddLengthSubarrays(arr));
    }

    public int sumOddLengthSubarrays(int[] arr) {
        int length = arr.length;
        int[] multiArr = new int[length];
        for (int i = 0; i < length; i += 2) {
            for (int j = 0; j + i < length; j++) {
                multiArr[j] += 1;
                if (j + i + 1 < length) {
                    multiArr[j + i + 1] -= 1;
                }
            }
        }
        int sum = multiArr[0] * arr[0];
        for (int i = 1; i < multiArr.length; i++) {
            multiArr[i] += multiArr[i - 1];
            sum += multiArr[i] * arr[i];
        }
        return sum;
    }
}
